#include"AVLtree.h"

template<class T, class Compare = less<T>>
class set
{
public:
    typedef T K;
protected:

    struct set_key_of_T
    {
        const K& operator()(const T& t) const
        {
            return t;
        }
    };

    // 存储的元素类型加上const，防止修改
    typedef AVLtree<K, const T, set_key_of_T, Compare> tree_type;
    tree_type _t;

public:
    set(){}
    set(initializer_list<T> il)
    {
        for(auto& e : il)
            _t.insert(e);
    }
    template<class InputIterator>
    set(InputIterator first, InputIterator last)
    {
        while(first != last)
        {
            _t.insert(*first);
            ++first;
        }
    }
    typedef tree_type::iterator         iterator;
    typedef tree_type::const_iterator   const_iterator;
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    const_iterator begin() const { return _t.begin(); }
    const_iterator end() const { return _t.end(); }

    // 注意set的find与AVL的find不同
    // AVL的find：找到了返回对应权值的迭代器，否则返回其父节点的迭代器
    // set的find：找到了返回对应权值的迭代器，否则返回end()
    iterator find(const K& key)
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(!cmp(*it, key) && !cmp(key, *it))    // *it == key
            return it;
        return _t.end();
    }

    // 新增const类型的find
    const_iterator find(const K& key) const
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(!cmp(*it, key) && !cmp(key, *it))    // *it == key
            return it;
        return _t.end();
    }

    int count(const K& key) const
    {
        return find(key) != end();
    }

    // 查询set中 >= key的最小的元素
    iterator lower_bound(const K& key)
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);     // 存在key，返回的就是key；否则只能是key的前驱/后继
        if(cmp(*it, key))   // *it < key
            ++it;
        return it;
    }
    // 新增const类型的lower_bound
    const_iterator lower_bound(const K& key) const
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);     // 存在key，返回的就是key；否则只能是key的前驱/后继
        if(cmp(*it, key))   // *it < key
            ++it;
        return it;
    }
    // 查询set中 > key的最小的元素
    iterator upper_bound(const K& key)
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(cmp(key, *it))   // *it > key
            return it;
        return ++it;
    }
    // 新增const类型的upper_bound
    const_iterator upper_bound(const K& key) const
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(cmp(key, *it))   // *it > key
            return it;
        return ++it;
    }

    pair<iterator, bool> insert(const T& val)
    {
        int old_size = _t.size();
        auto it = _t.insert(val);
        if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
            return {it, false};
        else 
            return {it, true};
    }
    int erase(const K& key) { return _t.erase(key); }

    int size() const { return _t.size(); }
    bool empty() const { return _t.empty(); }
    void clear() { return _t.clear(); }
};

template<class K, class V, class Compare = less<K>>
class map
{
protected:
    typedef pair<const K, V> T; // 防止key被修改，这里加上const

    struct map_key_of_T
    {
        const K& operator()(const T& t) const
        {
            return t.first;
        }
    };
    typedef AVLtree<K, T, map_key_of_T, Compare> tree_type;
    tree_type _t;

public:
    map(){}
    map(initializer_list<T> il)
    {
        for(auto& e : il)
            _t.insert(e);
    }
    template<class InputIterator>
    map(InputIterator first, InputIterator last)
    {
        while(first != last)
        {
            _t.insert(*first);
            ++first;
        }
    }
    typedef tree_type::iterator         iterator;
    typedef tree_type::const_iterator   const_iterator;
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    const_iterator begin() const { return _t.begin(); }
    const_iterator end() const { return _t.end(); }

    // 注意set的find与AVL的find不同
    // AVL的find：找到了返回对应权值的迭代器，否则返回其父节点的迭代器
    // set的find：找到了返回对应权值的迭代器，否则返回end()
    iterator find(const K& key)
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(!cmp(it->first, key) && !cmp(key, it->first))    // *it == key
            return it;
        return _t.end();
    }

    // 新增const类型的find
    const_iterator find(const K& key) const
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(!cmp(it->first, key) && !cmp(key, it->first))    // *it == key
            return it;
        return _t.end();
    }

    int count(const K& key) const
    {
        return find(key) != end();
    }

    iterator lower_bound(const K& key)
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);     // 存在key，返回的就是key；否则只能是key的前驱/后继
        if(cmp(it->first, key))   // *it < key
            ++it;
        return it;
    }
    // 新增const类型的lower_bound
    const_iterator lower_bound(const K& key) const
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);     // 存在key，返回的就是key；否则只能是key的前驱/后继
        if(cmp(it->first, key))   // *it < key
            ++it;
        return it;
    }
    iterator upper_bound(const K& key)
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(cmp(key, it->first))   // *it > key
            return it;
        return ++it;
    }
    // 新增const类型的upper_bound
    const_iterator upper_bound(const K& key) const
    {
        if(_t.empty()) return _t.end();

        Compare cmp;
        auto it = _t.find(key);
        if(cmp(key, it->first))   // *it > key
            return it;
        return ++it;
    }

    pair<iterator, bool> insert(const T& val)
    {
        int old_size = _t.size();
        auto it = _t.insert(val);
        if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
            return {it, false};
        else 
            return {it, true};
    }

    V& operator[](const K& key)
    {
        return insert({key, V()}).first->second;
    }

    int erase(const K& key) { return _t.erase(key); }

    int size() const { return _t.size(); }
    bool empty() const { return _t.empty(); }
    void clear() { return _t.clear(); }
};